class Solution:
    def countArrangement(self, n: int) -> int:
        def backtrack(index, used):
            if index > n:
                return 1
            count = 0
            for num in range(1, n + 1):
                if not used[num] and (num % index == 0 or index % num == 0):
                    used[num] = True
                    count += backtrack(index + 1, used)
                    used[num] = False
            return count
        used = [False] * (n + 1)
        return backtrack(1, used)
